Search results for "line covering problem"

Kvantu algoritmi punktu sadalīšanai pa taisnēm

2021

Bakalaura darba mērķis ir uzlabot klasisko algoritmu punktu sadalīšanai pa taisnēm, pielietojot kvantu algoritmus. Darbā tiek apskatīti klasiskie algoritmi punktu sadalīšanas problēmai un sadalīšanas problēmas speciālgadījumam, kad punktu izvietošanā atbilsts daļiņu pozīcijai pēc sadursmes lielā hadronu paātrinātājam. Darba rezultātā tiek piedāvāti kvantu algoritmi ar sarežģītību O(n^(1+(k-1)/k)/k) pamata problēmai un O(n^1.5/√k log⁡(n/k) ) speciālgadījumam. Dotie algoritmi uzlabo efektīvāko zināmo klasisko algoritmu, kuram darbības laiks ir O(n^2/k*log⁡(n/k) ). Secinājumos tiek piedāvāts paņēmiens, ka pielietot speciālgadījuma rezultātus reālajam daļiņu ceļu atrašanas uzdevumam, kad daļiņu…